package com.zhj.structure.hash.utils;

/**
 * @PackageName:com.zhj.structure.hash.utils
 * @ClassName:HashMap
 * @auter: 朱慧杰
 * @date:2020/8/13 0013 20:26
 **/
public class HashMap<K,V> {

    private static final int DEFAULT_SIZE = 1 << 4;  // 2的4次方  也就是16  一定要是2的整数次幂 减少hash 冲突
    private Entry<K,V>[] data;  // 存hash表
    private int size = 0; // 存了多少数
    private int cap;

    public HashMap() {
        this(DEFAULT_SIZE);
    }
    public HashMap(int cap) {  // 2的整数次幂 减少hash 冲突
        if (cap > 0) {
            data = new Entry[cap];
            size = 0;
            this.cap = cap;
        }
    }

    private int hash(K key) {
        int h = 0;
        if (key == null) h = 0;
        else {
            h = key.hashCode() ^ (h >>> 16);   // 16 位的无符号右移       ^ 异或
        }
        return h % cap;
    }

    public void put(K key,V value) {
        // key value 可以为null
        int hash = hash(key);
        Entry<K,V> newE = new Entry<>(key,value,null);
        Entry<K,V> hashM = data[hash];
        /**
         * 如果链表的size > 8 转红黑树
         */
        while (hashM != null) {
            if (hashM.key.equals(key)) {
                hashM.value = value;
                return;
            }
            hashM = hashM.next; // 链表的遍历
        }
        // 如果没有就相当于链表的插入
        newE.next = data[hash];
        data[hash] = newE;
        size++;

        /**
         * 这里还有一个扩容 size >= 我们的负载因子*空间数的时候 就要扩容
         * resize
         */
    }

    public V get(K key) {
        int hash = hash(key);
        Entry<K,V> entry = data[hash];
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }

    /**
     * 数据结构
     * @param <K>
     * @param <V>
     */
    private class Entry<K,V>{
        K key;
        V value;

        Entry<K,V> next;
        int cap; // 表示个数

        // 构造
        public Entry(K key, V value, Entry<K,V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

}
